/* 
 * $Id: TreeNode.java 1259 2007-01-09 14:23:47Z tcoupaye $
 *
 * Behavior Protocols extensions for static and runtime checking
 * developed for the Julia implementation of Fractal.
 *
 * Copyright 2004
 *    Distributed Systems Research Group
 *    Department of Software Engineering
 *    Faculty of Mathematics and Physics
 *    Charles University, Prague
 *
 * Copyright (C) 2006
 *    Formal Methods In Software Engineering Group
 *    Institute of Computer Science
 *    Academy of Sciences of the Czech Republic
 *
 * Copyright (C) 2006 France Telecom
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
 *
 * Contact: ft@nenya.ms.mff.cuni.cz
 * Authors: Jan Kofron <kofron@nenya.ms.mff.cuni.cz>
 */

package org.objectweb.fractal.bpc.checker.node;

import java.util.TreeSet;

import org.objectweb.fractal.bpc.checker.DFSR.CheckingException;
import org.objectweb.fractal.bpc.checker.state.*;
import org.objectweb.fractal.bpc.checker.utils.AnotatedProtocol;


/**
 * This class represents the node of a tree describing the state space of an
 * "execution".
 */
abstract public class TreeNode implements Cloneable {

    /** Creates a new instance of TreeNode */
    public TreeNode(String protocol) {
        this.protocol = protocol;
        weight = -1;
    }

    /**
     * @return the expected weight of this node, i.e. the size of automaton
     *         generated by its subtree.
     */
    abstract public long getWeight();

    /**
     * @return the vector of node's children.
     */
    public TreeNode[] getChildren() {
        return nodes;
    }

    /**
     * Changes the pointer at position of index to the newChild.
     */
    public void changeChild(int index, TreeNode newChild) throws ArrayIndexOutOfBoundsException {
        nodes[index] = newChild;
    }

    /**
     * Performs the forward cutting optimalization for this node. This is the
     * default implementation for the majority of node types
     * 
     * @param livingevents
     *            the already active events
     * @return the "optimized" tree, i.e. without some nodes and edges
     */
    public TreeNode forwardCut(TreeSet livingevents) {
        TreeNode active = null;
        int cnt = 0;

        for (int i = 0; i < nodes.length; ++i) {
            nodes[i] = nodes[i].forwardCut(livingevents);
            if (nodes[i] != null) {
                ++cnt;
                active = nodes[i];
            }
        }

        // no child node's survived
        if (cnt == 0)
            return null;

        // only one child node's survived and it hasn't been the only child
        // else we have to return the original node
        else if ((cnt == 1) && (nodes.length > 1))
            return active;

        // some of the child nodes have died
        else if (nodes.length != cnt) {
            TreeNode[] newchildren = new TreeNode[cnt];

            for (int i = 0, j = 0; i < cnt; ++i) {
                while (nodes[j] == null)
                    ++j;

                newchildren[i] = nodes[j++];
            }

            nodes = newchildren;

        }

        return this;
    }

    /**
     * This method creates a new (deep) copy of this node. This is needed for forward
     * cutting optimization.
     * 
     * @return the deepcopy of this node
     */
    public TreeNode copy() {
        TreeNode newnode = null;
        try {
            newnode = (TreeNode) this.clone();
        } catch (CloneNotSupportedException e) {
            return null;
        }

        newnode.nodes = new TreeNode[this.nodes.length];

        for (int i = 0; i < this.nodes.length; ++i) {
            newnode.nodes[i] = this.nodes[i].copy();
        }

        return newnode;
    }
    
    /**
     * Counts the number of leaves of this subtree
     * @return	the number of leaves
     */
    public int getLeafCount() {
        int cnt = 0;
        for (int i = 0; i < nodes.length; ++i)
            cnt += nodes[i].getLeafCount();
        
        return cnt;
    }
    
    /**
     * @return AnotatedProtocol for printing and error trace understanding.
     */
    abstract public AnotatedProtocol getAnotatedProtocol(State state);

    //--------------------------------------------------------------------------
    /**
     * @return the initial state of the automat
     */
    abstract public State getInitial();

    /**
     * @return true if this is an accepting state, false otherwise
     */
    abstract public boolean isAccepting(State state);

    /**
     * Retrieve the list of transition from a given state
     * 
     * @param state find all transitions from this state
     * @return the list of pairs of transitions (and their names)
     * @throws InvalidParameterException	means internal error - bad parameter passed to an eventnode
     * @throws CheckingException		means a composition error was detected
     */
    abstract public TransitionPairs getTransitions(State state) throws InvalidParameterException, CheckingException;

    /**
     * @return the symbolic name of the treenode denoting its type
     */
    abstract public String[] getTypeName();

    //--------------------------------------------------------------------------
    /** private attributes */

    /**
     * Child nodes of this node
     */
    protected TreeNode[] nodes;

    /**
     * The weight of the node - it is counted in a lazy way
     */
    protected long weight;

    /**
     * The protocol represented by this node
     */
    public String protocol;

}

